NSF PAR Search | NSF Public Access Repository

Given a set $$P$$ of $$n$$ points in the plane, and a parameter $$k$$, we present an algorithm, whose running time is $$O(n^{3/2} \sqrt{k}\log^{3/2} n + kn\log^2 n)$$, with high probability, that computes a subset $$Q* \subseteq P$$ of $$k$$ points, that minimizes the Hausdorff distance between the convex-hulls of $Q*$ and $$P$$. This is the first subquadratic algorithm for this problem if $$k$$ is small.

Clustering with Neighborhoods is Hard for Squares

Klimenko, Georgiy; Raichel, Benjamin (July 2023, Proceedings of the 35th Canadian Conference on Computational Geometry)

Pankratov, Denis (Ed.)

In the clustering with neighborhoods problem one is given a set S of disjoint convex objects in the plane and an integer parameter k ≥ 0, and the goal is to select a set C of k center points in the plane so as to minimize the maximum distance of an object in S to its nearest center in C. Previously [HKR21] showed that this problem cannot be approximated within any factor when S is a set of disjoint line segments, however, when S is a set of disjoint disks there is a roughly 8.46 approximation algorithm and a roughly 6.99 approximation lower bound. In this paper we investigate this significant discrepancy in hardness between these shapes. Specifically, we show that when S is a set of axis aligned squares of the same size, the problem again is hard to approximate within any factor. This surprising fact shows that the discrepancy is not due to the fatness of the object class, as one might otherwise naturally suspect.

Full Text Available

Search for: All records